package com.mdnote.practice.disjointed_set;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/24
 * @description  岛屿数量
 */
public class LeetCode200 {

    public static void main(String[] args) {
        char[][] M = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        LeetCode200 LeetCode200 = new LeetCode200();
        int res = LeetCode200.numIslands(M);
        System.out.println(res);
    }

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        // 以长的那条为边，看做正方形
        int[] parent = new int[grid.length * grid[0].length];

        int island_count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    parent[i * grid[0].length + j] = i * grid[0].length + j;
                    island_count++;
                }
            }
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    // 沉岛
                    grid[i][j] = '0';
                    // 合并四个方向
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                        if (union((i - 1) * grid[0].length + j, i * grid[0].length + j, parent) == 0) {
                            island_count--;
                        };
                    }
                    if (i + 1 < grid.length && grid[i + 1][j] == '1') {
                        if (union((i + 1) * grid[0].length + j, i * grid[0].length + j, parent) == 0) {
                            island_count--;
                        };
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                        if (union(i * grid[0].length + j, i * grid[0].length + j - 1, parent) == 0) {
                            island_count--;
                        };
                    }
                    if (j + 1 < grid[0].length && grid[i][j + 1] == '1') {
                        if (union(i * grid[0].length + j, i * grid[0].length + j + 1, parent) == 0) {
                            island_count--;
                        };
                    }
                }
            }
        }
        return island_count;
    }

    public int find_parent(int x, int[] parent) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }

    public int union(int x, int y, int[] parent) {
        int x_root = find_parent(x, parent);
        int y_root = find_parent(y, parent);
        if (x_root == y_root) {
            return -1;
        } else {
            // 把x的树合并到y上
            parent[x_root] = y_root;
            return 0;
        }
    }
}
